#!/usr/bin/env python

'''
    MUDServ - A Multi-User Dungeon Server
    World Map Class Source Code
    
    Copyright (c) 2009, Ecl3ctic Software
    All rights reserved.
    
    Redistribution and use in source and binary forms, with or without
    modification, are permitted provided that the following conditions are met:

    * Redistributions of source code must retain the above copyright notice,
        this list of conditions and the following disclaimer.
    * Redistributions in binary form must reproduce the above copyright notice,
        this list of conditions and the following disclaimer in the documentation
        and/or other materials provided with the distribution.
    * Neither the name of Ecl3ctic Software nor the names of its contributors
        may be used to endorse or promote products derived from this software
        without specific prior written permission.

    THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
    AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
    IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
    ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
    LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
    CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
    SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
    INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
    CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
    ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
    POSSIBILITY OF SUCH DAMAGE.
'''

import simplejson
import mutex
from random import *
from ConfigParser import *
from model import *
from time import sleep

__version__ = '04-12-09'
__author__ = 'Ian Wagner and Michael Chest'
__credits__ = ['Ian Wagner', 'Michael Chest', 'Brian McBrayer', 'Dan Alexander',
               'Zak Richards', 'Reuben Deleon']
__license__ = 'BSD'
__status__ = 'Development'
__copyright__ = 'Copyright 2009 Ecl3ctic Software'

# Symbolic constants for directions
NORTH = 0
EAST = 1
SOUTH = 2
WEST = 3

# Symbolic constants for feature tuple indices
X = 0
Y = 1
HEIGHT = 2
WIDTH = 3
TYPE = 4
CONNECTIONS = 5

# Symbolic constants for feature types
ROOM = 0
PASSAGE = 1
RANDOM = 2    # ONLY used as an argument for addFeature

# Symbolic constants for exit direction
NONE = 0
UP = 1
DOWN = 2

DIR = 2   # for exit tuple access

lock = mutex.mutex()    # Lock to make sure we don't generate duplicate boards or anything like that

class BoardGenerator:
  '''
    A class that... well... generates boards :)
  '''
  def __init__(self):
    self.board = [[' ' for i in range(80)] for i in range(24)]
    self.features = []         # List of tuples (x, y, height, width, type, [list of walls with features connected]) to keep track of features
    self.spawnX = 0
    self.spawnY = 0
    
    config = SafeConfigParser()
    config.readfp(open('server.cfg'))
    
    self.passageMaxLen = config.getint('worldmap', 'passage_maxlen')
    
  def generateRect(self, height, width):
    '''
      Generates a rectangle with a given size.
      
      The feature is returned as a 2-D list;
    '''
    rect = [['#' for i in range(width)] for i in range(height)]
    
    for i in range(1, height - 1):
      for j in range(1, width - 1):
        rect[i][j] = ' '
        
    return rect
    
  def addPassage(self, featureIndex, side, length):
    '''
      Adds a passage to the feature in the board (described by a feature tuple),
      on the specified side with given length.
    '''
    x = 0
    y = 0
    height = 0
    width = 0
    opening = (0, 0)
    feature = self.features[featureIndex]
    
    success = False
    fails = 0
    maxFails = 15
    
    # Attempt to add a passage
    while not success and fails < maxFails:
      if side == NORTH:
        # North extension
        x = randint(feature[X] + 1, feature[X] + feature[WIDTH] - 4)
        y = feature[Y] - length - 1
        height = length + 2
        width = 3
        opening = (x + 1, y + height - 1)
        connected = [SOUTH]
      elif side == EAST:
        # East extension
        x = feature[X] + feature[WIDTH] - 1
        y = randint(feature[Y] + 1, feature[Y] + feature[HEIGHT] - 4)
        height = 3
        width = length + 2
        opening = (x, y + 1)
        connected = [WEST]
      elif side == SOUTH:
        # South extension
        x = randint(feature[X] + 1, feature[X] + feature[WIDTH] - 4)
        y = feature[Y] + feature[HEIGHT] - 1
        height = length + 2
        width = 3
        opening = (x + 1, y)
        connected = [NORTH]
      elif side == WEST:
        # West extension
        x = feature[X] - length - 1
        y = randint(feature[Y] + 1, feature[Y] + feature[HEIGHT] - 4)
        height = 3
        width = length + 2
        opening = (x + length + 1, y + 1)
        connected = [EAST]
      
      success = self.canAddFeature(featureIndex, x, y, height, width)
      fails += 1
    if fails == maxFails:
      return False
      
    # Add the passage
    passage = self.generateRect(height, width)
    self.pasteIn(passage, x, y)
    self.board[opening[1]][opening[0]] = ' '
    self.features.append((x, y, height, width, PASSAGE, connected))
    self.features[featureIndex][CONNECTIONS].append(side)
    return True
    
  def canAddPassage(self, featureIndex, side, length):
    '''
      Checks if a passage can be added off of a room in board
    '''
    height = len(self.board)
    width = len(self.board[0])
    feature = self.features[featureIndex]
    
    if side in feature[CONNECTIONS] or feature[TYPE] != ROOM:
      return False
    elif side == NORTH:
      # North
      if feature[Y] - length - 2 <= 0 or feature[X] + 6 > feature[X] + feature[WIDTH]:
        return False
    elif side == EAST:
      # East
      if feature[X] + feature[WIDTH] + length + 2 >= width or feature[Y] + 5 > feature[Y] + feature[HEIGHT]:
        return False
    elif side == SOUTH:
      # South
      if feature[Y] + feature[HEIGHT] + length + 2 >= height or feature[X] + 5 > feature[X] + feature[WIDTH]:
        return False
    elif side == WEST:
      # West
      if feature[X] - length - 2 <= 0 or feature[Y] + 5 > feature[Y] + feature[HEIGHT]:
        return False
    else:
      return False
    
    return True
    
  def canAddFeature(self, featureIndex, x, y, height, width):
    '''
      Checks if a room can be added off another feature (must be a passage)
    '''
    feature = self.features[featureIndex]
    
    if ((x + width + 2 >= len(self.board[0])) or (y + height + 2 >= len(self.board)) or (x < 0) or (y < 0)):
      return False
    
    # Check to make sure we aren't overwriting anything
    try:
      for i in range(1, height + 1):
        for j in range(1, width + 1):
          if self.board[i + y][j + x] != ' ':
            return False
    except:
      return False
    
    return True
    
  def addRoom(self, featureIndex):
    '''
      Adds a room to the passage described in self.features[featureIndex]
    '''
    maxFails = 20             # Max fails to add a feature to the map before giving up
    feature = self.features[featureIndex]
    
    if feature[TYPE] != PASSAGE:
      return False
    
    minX = 0
    maxX = 0
    minY = 0
    maxY = 0
    
    # * Determine the minimum and maximum ranges for (x, y) of the top-left
    #   corner of the room
    # * Determine the formulas for minimum and maximum height based on those values
    # * Determine which connections will be added
    # * Determine which tile to knock out for the opening
    if feature[CONNECTIONS] == [SOUTH]:
      # Attach south of room to north of passage
      minX = feature[X] - 10
      maxX = feature[X] - 5
      minY = feature[Y] - 10
      maxY = feature[Y] - 5
      minHeight = 'feature[Y] - y + 1'
      maxHeight = minHeight
      minWidth = 'abs(feature[X] - x) + 5'
      maxWidth = 'abs(feature[X] - x) + 15'
      passageConn = NORTH
      roomConn = SOUTH
      opening = (feature[X] + 1, feature[Y])
    elif feature[CONNECTIONS] == [NORTH]:
      # Attach north of the room to south of passage
      minX = feature[X] - 10
      maxX = feature[X] - 5
      minY = feature[Y] + feature[HEIGHT] - 1
      maxY = feature[Y] + feature[HEIGHT] - 1
      minHeight = '5'
      maxHeight = '10'
      minWidth = 'abs(feature[X] - x) + 5'
      maxWidth = 'abs(feature[X] - x) + 15'
      passageConn = SOUTH
      roomConn = NORTH
      opening = (feature[X] + 1, feature[Y] + feature[HEIGHT] - 1)
    elif feature[CONNECTIONS] == [WEST]:
      # Attach west of room to east of passage
      minX = feature[X] + feature[WIDTH] - 1
      maxX = feature[X] + feature[WIDTH] - 1
      minY = feature[Y] - 10
      maxY = feature[Y] - 5
      minHeight = 'abs(feature[Y] - y) + 5'
      maxHeight = 'abs(feature[Y] - y) + 10'
      minWidth = '5'
      maxWidth = '15'
      passageConn = EAST
      roomConn = WEST
      opening = (feature[X] + feature[WIDTH] -1, feature[Y] + 1)
    elif feature[CONNECTIONS] == [EAST]:
      # Attach east of room to west of passage
      minX = feature[X] - 10
      maxX = feature[X] - 5
      minY = feature[Y] - 10
      maxY = feature[Y] - 5
      minHeight = 'abs(feature[Y] - y) + 5'
      maxHeight = 'abs(feature[Y] - y) + 10'
      minWidth = 'feature[X] - x + 1'
      maxWidth = minWidth
      passageConn = WEST
      roomConn = EAST
      opening = (feature[X], feature[Y] + 1)
    else:
      return False
    
    if minX < 0 or minY < 0:
      return False
    
    # Generate the (x, y) coordinate for the top-left corner, height, and width
    x = randint(minX, maxX)
    y = randint(minY, maxY)
    height = randint(eval(minHeight), eval(maxHeight))
    width = randint(eval(minWidth), eval(maxWidth))
    
    # Make sure that it is ok to put the room there, and if not re-compute
    fails = 0
    while not self.canAddFeature(featureIndex, x, y, height, width) and fails < maxFails * 3:
      x = randint(minX, maxX)
      y = randint(minY, maxY)
      height = randint(eval(minHeight), eval(maxHeight))
      width = randint(eval(minWidth), eval(maxWidth))
      fails += 1
      
    if fails == maxFails * 3:
      return False
      
    # Finally, we are clear to add the room to the map
    self.features.append((x, y, height, width, ROOM, [roomConn]))
    self.features[featureIndex][CONNECTIONS].append(passageConn)
    room = self.generateRect(height, width)
    self.pasteIn(room, x, y)
    self.board[opening[1]][opening[0]] = ' '
    
    return True
    
  def overlaps(self, x, y, height, width):
    '''
      Checks if one feature starting at (x, y) with height and width will overlap
      existing features
    '''
    for i in range(height):
      for j in range(width):
        try:
          if self.board[i + y][j + x] == '#':
            return True
        except:
          return True
        
    return False
    
  def pasteIn(self, src, x, y):
    '''
      "Paints" the contents of src on top of self.board starting at (x, y) and
      decreasing down and to the right.
      
      Both src and dest are 2-D lists.
    '''
    error = ''
    for i in range(len(src)):
      for j in range(len(src[0])):
        try:
          self.board[i + y][j + x] = src[i][j]
        except IndexError:
          error += 'i: %d j: %d i+y: %d j+x: %d\n' % (i, j, i + y, j + x)
          pass
    if (error):
      print error
    
  def addRandomFeature(self, type=RANDOM):
    maxFails = 20             # Max fails to add a feature to the map before giving up
    
    if type == RANDOM:
      type = randint(0, 1)    # Decide what type of feature to add
    
    side = randint(0, 3)
    featureIndex = randint(0, len(self.features) - 1)
    fails = 0
    
    if type == PASSAGE:
      # Add a passage
      length = randint(3, 8)
      
      while not self.canAddPassage(featureIndex, side, length) and fails < maxFails:
        length = randint(3, 8)
        side = randint(0, 3)
        fails += 1
      if fails == maxFails:
        return False
      
      return self.addPassage(featureIndex, side, length)
    elif type == ROOM:
      # Add a room
      
      # Check that the type of feature is a passage with only one existing connection
      while (((self.features[featureIndex][TYPE] != PASSAGE) or (len(self.features[featureIndex][CONNECTIONS]) != 1)) and (fails < maxFails)):
        featureIndex = randint(0, len(self.features) - 1)
        fails += 1
      if fails == maxFails:
        return False
      
      self.addRoom(featureIndex)
    
  def addExit(self, exit):
    '''
      Adds an exit described by the exit tuple in the form (X, Y, DIR) to the
      map
    '''
    x = 0
    y = 0
    opening = (0, 0)
    
    if exit[DIR] == UP:
      self.board[Y][X] = 'U'
    elif exit[DIR] == DOWN:
      self.board[Y][X] = 'D'
    else:
      if exit[Y] == 0:
        # Start at north end of board
        x = exit[X] - 1
        y = exit[Y]
        height = 3
        width = 3
        
        try:
          while not self.overlaps(x, y, height, width):
            height += 1
          
          if self.board[y + height - 1][x] != '#' or self.board[y + height - 1][x + 1] != '#' or self.board[y + height - 1][x + 2] != '#':
            return False
        except:
          return False
        
        openings = [(exit[X], exit[Y]), (exit[X], exit[Y] + height - 1)]
        
      elif exit[Y] == len(self.board) - 1:
        # Start at south end of board
        x = exit[X] - 1
        y = exit[Y] - 2
        height = 3
        width = 3
        
        try:
          while not self.overlaps(x, y, height, width):
            y -= 1
            height += 1
            
          if self.board[y][x] != '#' or self.board[y][x + 1] != '#' or self.board[y][x + 2] != '#':
            return False
        except:
          return False
          
        openings = [(exit[X], exit[Y]), (exit[X], y)]
        
      elif exit[X] == 0:
        # Start at west end of board
        x = exit[X]
        y = exit[Y] - 1
        height = 3
        width = 3
        
        try:
          while not self.overlaps(x, y, height, width):
            width += 1
          
          if self.board[y][x + width - 1] != '#' or self.board[y + 1][x + width - 1] != '#' or self.board[y + 2][x + width - 1] != '#':
            return False
        except:
          return False
        
        openings = [(exit[X], exit[Y]), (exit[X] + width - 1, exit[Y])]
        
      elif exit[X] == len(self.board[0]) - 1:
        # Start at east end of board
        x = exit[X] - 3
        y = exit[Y] - 1
        height = 3
        width = 3
        
        try:
          while not self.overlaps(x, y, height, width):
            x -= 1
            width += 1
          
          if self.board[y][x] != '#' or self.board[y + 1][x] != '#' or self.board[y + 2][x] != '#':
            return False
        except:
          return False
          
        openings = [(exit[X] - width, exit[Y]), (exit[X]  - 1, exit[Y])]
      
      passage = self.generateRect(height, width)
      self.pasteIn(passage, x, y)
      try:
        for opening in openings:
          self.board[opening[Y]][opening[X]] = '+'
      except:
        pass
      return True
    
  def generateBoard(self, spawnX, spawnY, height, width, exits=[]):
    '''
      Generates a random board in teh roguelike style
      
      spawnX and spawnY - x and y dimensions of main spawn coordinate
      height and width - height and width of the board area
      exits - a list of tuples in the form (X, Y, DIR) specifying an entrance/exit
        location's coordinates and direction. Possible values for DIR are defined
        by the constants NONE, UP, DOWN (0, 1, 2)
    '''
    self.features = []      # List of tuples (x, y, height, width) to keep track of features
    
    while len(self.features) < 15:
      self.board = [[' ' for i in range(width)] for i in range(height)]
      self.features = []      # List of tuples (x, y, height, width) to keep track of features
      self.spawnX = spawnX
      self.spawnY = spawnY
      
      if spawnX >= width - 5 or spawnX <= 5 or spawnY >= height - 5 or spawnY <= 5:
        return self.board
      
      # Create the start feature
      x = randint(spawnX - 5, spawnX - 2)
      y = randint(spawnY - 4, spawnY - 1)
      featureHeight = randint(6, min(10, height - y - 1))
      featureWidth = randint(6, min(10, width - x - 1))
      self.features.append((x, y, featureHeight, featureWidth, ROOM, []))
      
      startfeature = self.generateRect(featureHeight, featureWidth)
      self.pasteIn(startfeature, x, y)
      
      self.board[spawnY][spawnX] = 'S';
      
      # Add some passages
      self.addRandomFeature(PASSAGE)
      self.addRandomFeature(PASSAGE)
      self.addRandomFeature(ROOM)
      
      # Randomly add a reasonable amount of features
      nLoops = 3
      
      for i in range(nLoops):
        fails = 0
        maxFails = 25
        while fails < maxFails:
          success = self.addRandomFeature()
          if not success:
            fails += 1
        
        # Attempt to add rooms onto the end of passages
        for featureIndex in range(len(self.features)):
          self.addRoom(featureIndex)
      
        # Attempt to add rooms onto the end of passages (one last time lol)
        for featureIndex in range(len(self.features)):
          self.addRoom(featureIndex)
          
      # Add in the exits
      for exit in exits:
        if not self.addExit(exit):
          self.features = []    # Force map re-build
    
    return self.board
    
  def getJSONBoard(self):
    '''
      Returns the JSON stringified representation of self.board
    '''
    board = {}
    
    board['height'] = len(self.board)
    board['width'] = len(self.board[0])
    board['spawn'] = {}
    
    for i in range (len(self.board)):
      for j in range(len(self.board[0])):
        if self.board[i][j] != ' ':
          if not board.has_key(str(i)):
            board[str(i)] = {}
          c = self.board[i][j]
          if c in 'SUD+':    # if c is S, U, or D (spawn, up, down)
            spawnPoint = {'x': j, 'y': i}
            
            # Determine which spawn point this is
            if c == 'U':
              point = 'up'
            elif c == 'D':
              point = 'down'
            elif i == 0:
              point = 'north'
            elif i == len(self.board) - 1:
              point = 'south'
            elif j == 0:
              point = 'west'
            elif j == len(self.board[0]) - 2:
              point = 'east'
            elif c == 'S':
              point = 'main'
            else:
              board[str(i)][str(j)] = {'ascii': c}
              continue
            
            board['spawn'][point] = spawnPoint
            if c != 'S':
              board[str(i)][str(j)] = {'ascii': '+'}
          else:
            board[str(i)][str(j)] = {'ascii': c}
    
    return simplejson.dumps(board)

class WorldMap:
  '''
    WorldMap for MUDServ
    
    This class will keep track of fetching and creating maps in the database
  '''
  def __init__(self):
    # Types of zones that are defined by the server. The client can render however
    # it desires
    self.zones = ['dungeon', 'overworld', 'forest']
    self.boardGen = BoardGenerator()
    
    config = SafeConfigParser()
    config.readfp(open('server.cfg'))
    
    self.boardHeight = config.getint('worldmap', 'board_height')
    self.boardWidth = config.getint('worldmap', 'board_width')
    
  def fetchBoard(self, x, y, z, canGenerate=True):
    '''
      Fetches the board located at point (x, y, z) in the game world.
      If canGenerate is True, a nonexistent board will be generated when
      requested.
    '''
    result = Board.query.filter_by(x=x, y=y, z=z).first()
    if not result and canGenerate:
      result = self.generateBoard(x, y, z, self.boardHeight, self.boardWidth)
    result = Board.query.filter_by(x=x).filter_by(y=y).filter_by(z=z).first()
    return result
    
  def generateBoard(self, x, y, z, height, width):
    '''
      Generates a board for position x, y, and z in the world space. Returns
      the model.Board object representing the newly created board.
    '''
    while not lock.testandset():
      sleep(0.1)
    # Make sure we don't already have a board here
    result = Board.query.filter_by(x=x).filter_by(y=y).filter_by(z=z).first()
    if result:
      lock.unlock()
      return result
    
    # Check where we need maps to link
    exits = []
    
    # Check North
    result = Board.query.filter_by(x=x).filter_by(y=y+1).filter_by(z=z).first()
    if result and simplejson.loads(result.data).get('spawn', {}).get('south', {}).get('x', None):
      exits.append((simplejson.loads(result.data).get('spawn').get('south').get('x'), 0, NONE))
    else:
      exits.append((randint(5, self.boardWidth - 5), 0, NONE))
      
    # Check South
    result = Board.query.filter_by(x=x).filter_by(y=y-1).filter_by(z=z).first()
    if result and simplejson.loads(result.data).get('spawn', {}).get('north', {}).get('x', None):
      exits.append((simplejson.loads(result.data).get('spawn').get('north').get('x'), self.boardHeight - 1, NONE))
    else:
      exits.append((randint(5, self.boardWidth - 5), self.boardHeight - 1, NONE))
      
    # Check East
    result = Board.query.filter_by(x=x+1).filter_by(y=y).filter_by(z=z).first()
    if result and simplejson.loads(result.data).get('spawn', {}).get('west', {}).get('y', None):
      exits.append((self.boardWidth - 1, simplejson.loads(result.data).get('spawn').get('west').get('y'), NONE))
    else:
      exits.append((self.boardWidth - 1, randint(5, self.boardHeight - 5), NONE))
    
    # Check West
    result = Board.query.filter_by(x=x-1).filter_by(y=y).filter_by(z=z).first()
    if result and simplejson.loads(result.data).get('spawn', {}).get('east', {}).get('y', None):
      exits.append((0, simplejson.loads(result.data).get('spawn').get('east').get('y'), NONE))
    else:
      exits.append((0, randint(5, height - 5), NONE))
      
    # Random note: spawning at (10, 10) seems to generate relatively good maps
    # efficiently as opposed to starting somewhere in the middle of the board
    # and trying to work outward since the generation is random
    gen = BoardGenerator()
    gen.generateBoard(10, 10, height, width, exits)
    
    board = Board(x=x, y=y, z=z, data=unicode(gen.getJSONBoard()), name=unicode('board (%d, %d, %d)' % (x, y, z)))
    session.commit()
    lock.unlock()
    return board
    
# Print out a random map and its JSON representation if this script is run by itself
if __name__ == '__main__':
  height = 50
  width = 90
  gen = BoardGenerator()
  exits = [(0, randint(5, height - 5), NONE), (randint(5, width - 5), 0, NONE), (width - 1, randint(5, height - 5), NONE), (randint(5, width - 5), height - 1, NONE)]
  board = '\n'.join([''.join(c) for c in gen.generateBoard(10, 10, height, width, exits)])
  print gen.getJSONBoard()
  print board